\documentclass[12pt]{beamer}

\mode<presentation>
{
  \usetheme{Warsaw}
}

\usepackage[utf8]{inputenc}
\usepackage{color}
\usepackage{epsfig}
\usepackage{alltt}
\usepackage{moreverb}

\newcommand{\red}[1]{\textcolor{red}{#1}}
\newcommand{\tr}[1]{\texttt{\red{#1}}}

\def\bs{$\backslash$}
\def\inputfig#1{\input #1}
\def\inputtex#1{\input #1}

\title{SICL spinoffs}
\author{Robert Strandh}

\institute{Université de Bordeaux}
\date[ILC 2014]{International Lisp Conference 2014}


\begin{document}

\begin{frame}
  \titlepage
\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Three papers}

  \begin{itemize}
  \item Fast generic dispatch for Common Lisp.
  \item An improvement to sliding garbage collection.
  \item Resolving metastability during bootstrapping.
  \end{itemize}
\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Contents of talk}

  \begin{itemize}
  \item Presentation of the SICL project.
  \item Fast generic dispatch.
  \item Sliding garbage collection.
  \item Resolving metastability.
  \item SICL, present and future.
  \end{itemize}
\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{SICL}

  SICL does not stand for anything.  Pronounce it ``sickle''.
  \vskip 0.25cm
  Reason for SICL: Review design decisions of existing
  implementations, in order to:
  
  \begin{itemize}
  \item Use more of CLOS.
  \item Make modules implementation independent.
  \item Improve algorithms.
  \item Prepare for internationalization. 
  \item Simplify the code. 
  \end{itemize}
\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{SICL}
  \framesubtitle{Examples of design decisions revisited}

  \begin{itemize}
  \item Implementation of \texttt{:from-end t} on list sequences.
  \item In-place \emph{merge sort} algorithm. 
  \item Representation of heap-allocated objects.
  \item Use first-class global environments.
  \item Using CLOS for built-in classes.
  \item CLOS generic dispatch.
  \item Garbage collection.
  \item CLOS bootstrapping.
  \end{itemize}
\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{SICL}
  \framesubtitle{Object representation}
  \begin{center}
\inputfig{fig-representation.pdf_t}
  \end{center}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{SICL}
  \framesubtitle{Object representation}

  Our representation has several advantages:

  \begin{itemize}
  \item Objects are double-word aligned, leaving 3 tag bits on 32-bit
    machines and 4 tag bits on 64-bit machines.  
  \item The rack is \emph{internally consistent}, making \emph{lock
    free updates} possible (using \emph{compare-and-swap}
    instruction).
  \item Non-simple arrays can be adjusted. 
  \item Global garbage collector can be both non-moving and
    compacting.
  \item Uniform treatment of standard objects and built-in instances. 
  \end{itemize}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{SICL}
  \framesubtitle{Object representation}

  Representation of a generic function:
  \vskip 0.25cm
  A \emph{call history} that maps class numbers of required arguments
  to effective methods. 
  \vskip 0.25cm
  The discriminating function is computed from the call history
  without invoking any MOP machinery. 

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Fast generic dispatch}
  \framesubtitle{Existing work}

  Most of the literature discusses table-based methods, which are not
  very well adapted to modern architectures.  Compressing the tables
  increases the number of memory accesses even more.
  \vskip 0.5cm
  PCL uses a simple hash table.
  \vskip 0.5cm
  Zendra \emph{et al} use a technique similar to ours, but only for
  static languages.

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Fast generic dispatch}
  \framesubtitle{Main idea}

  Main idea in work by Zendra \emph{et al}:

  \begin{itemize}
  \item Number the classes.
  \item Determine ``effective method'' by a binary search, comparing
    class number of argument to small integer constants.
  \end{itemize}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Fast generic dispatch}
  \framesubtitle{Challenge}

  Main challenge is to make it work for CL, given that:

  \begin{itemize}
  \item Classes can be dynamically redefined.
  \item Instances can become obsolete.
  \end{itemize}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Fast generic dispatch}
  \framesubtitle{Our method}

  \begin{itemize}
  \item Every object has an associated \emph{tag}, which is the class
    number when the object was created.
  \item Immediate objects, cons cells, and general instances of
    built-in classes always have the same tag as the class number.
  \item The tag of a general instance is stored in the rack of the
    instance. 
  \end{itemize}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Fast generic dispatch}
  \framesubtitle{Our method}

  When a class changes:

  \begin{itemize}
  \item Allocate a new number for it.
  \item Remove effective methods containing methods that specialize on
    it from call histories.
  \item Set the discriminating function to some default that
    recomputes itself from the call history.
  \end{itemize}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Fast generic dispatch}
  \framesubtitle{Our method}

  When a dispatch on an obsolete instance is attempted:

  \begin{itemize}
  \item The discriminating function will fail.
  \item Default action updates the instance. 
  \item The discriminating function is tried again.
  \item If it still fails, invoke general machinery.
  \end{itemize}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Fast generic dispatch}
  \framesubtitle{Results}

  Not yet implemented, but some experiments conducted:

  \begin{itemize}
  \item Simulated simple slot reader.
  \item Several comparisons.
  \item Large integers.
  \end{itemize}

Result: 3-5 times as fast as existing techniques.

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Fast generic dispatch}
  \framesubtitle{Consequences}

  \begin{itemize}
  \item With our method, generic dispatch is no slower than
    a ``manual'' type test.
  \item Therefore, generic functions can be used for built-in
    accessors such as \texttt{symbol-name},
    \texttt{package-nicknames}, etc.
  \item Generic dispatch could even be used for general arithmetic.
  \end{itemize}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Sliding garbage collection}
  \framesubtitle{Context of work}

  We imagine a collector with two generations:

  \begin{itemize}
  \item A per-thread \emph{nursery} the size of the cache.
  \item A global generation common to all threads.
  \end{itemize}

Global generation: Compactor by Karmany \emph{et al}.
\vskip 0.25cm
Nursery: Our sliding collector algorithm.

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Sliding garbage collection} 
  \framesubtitle{Original idea}

  Original algorithm by Haddon and Waite in 1967.
  \vskip 0.5cm
  Context: existing mark-and-sweep GC.
  \vskip 0.5cm
  Basic idea: construct a \emph{break table} that maps intervals of
  addresses to \emph{deltas} to be added to addresses in order to
  obtain new location. 

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Sliding garbage collection} 
  \framesubtitle{Example of break table}
  \begin{center}
\inputfig{fig-example-aa.pdf_t}
  \end{center}

  \begin{center}
\inputfig{fig-example-da.pdf_t}
  \end{center}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Sliding garbage collection} 
  \framesubtitle{Problem with original algorithm}

    Building the break table is expensive:

    \begin{itemize}
    \item Partially built table must be moved several times.
    \item Final table must be sorted.  
    \end{itemize}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Sliding garbage collection} 
  \framesubtitle{Bitmap for marking}

  Haddon and Waite did not consider marking (already done).  Existing
  marking might already use a bitmap.
  \vskip 1cm
  Use one bit per word:

  \begin{center}
\inputfig{fig-example-a.pdf_t}
  \end{center}
\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Sliding garbage collection} 
  \framesubtitle{Compaction}

  Compaction is straightforward:

  \begin{center}
\inputfig{fig-example-b.pdf_t}
  \end{center}

  \begin{center}
\inputfig{fig-example-c.pdf_t}
  \end{center}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Sliding garbage collection} 
  \framesubtitle{Build break table from bitmap}

  Building the break table is also straightforward:

  \begin{center}
\inputfig{fig-example-d.pdf_t}
  \end{center}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Sliding garbage collection} 
  \framesubtitle{Adjusting pointers}

  Adjusting pointers requires a binary search of the break table, but: 

  \begin{itemize}
  \item Break table has few entries because:
    \begin{itemize}
    \item We preserve allocation order.
    \item Objects that are allocated together, die together.
    \end{itemize}
  \item Caching is possible.  Table is not searched randomly, because: 
    \begin{itemize}
    \item We preserve allocation order.
    \item Objects that are allocated together, refer to each other.
    \end{itemize}
  \end{itemize}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{Sliding garbage collection}
  \framesubtitle{Timing}

Nursery size: 4MiB
\vskip 0.25cm
Clock speed: 1.6GHz
\vskip 0.25cm
Cache size: 6MiB
\vskip 0.5cm
\begin{tabular}{|l|r|r|}
  \hline
  Phase & Pessimistic (ms) & Educated guess (ms)\\
  \hline
  \hline
  Marking & ? & ?\\
  \hline
  Compaction & 1.4 &  0.3\\
  \hline
  Table   & 1.4 & 0.3 \\
  \hline
  Adjusting & 30 & 5 \\
  \hline
\end{tabular}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{CLOS Bootstrapping}
  \framesubtitle{Bootstrapping and metastability issues}

The AMOP distinguishes between two types of \emph{issues}:
\vskip 0.5cm
\begin{itemize}
\item Bootstrapping issues: The class \texttt{standard-class} must exist in
  order to be created.
\item Metastability issues: Attempting to compute the discriminating function
  of the function \texttt{compute-discriminating-function}.
\end{itemize}

Bootstrapping issues are easy to solve; metastability issues are hard.

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{CLOS Bootstrapping}
  \framesubtitle{Metastability issues}

Observation:
\vskip 0.5cm

The canonical example of metastability issue is an issue only if the
\emph{existing} discriminating function of
\texttt{compute-discriminating-function} is unable to compute the
discriminating function of a standard generic function.

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{CLOS Bootstrapping}
  \framesubtitle{Our technique}

We make sure that the initial discriminating function of every
\emph{specified generic function} can handle arguments of every
\emph{specified class}.
\vskip 0.5cm
We call this technique \emph{satiation}.

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{CLOS Bootstrapping}
  \framesubtitle{Call history of a generic function}

Recall:
\vskip 0.5cm

The call history contains the result of calling
\texttt{compute-applicable-methods-using-classes} and then
\texttt{compute-effective-method}.
\vskip 0.25cm
The discriminating function is an automaton computed from the call
history without calling any generic function.

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{CLOS Bootstrapping}
  \framesubtitle{Bootstrapping method used by SICL}

  \begin{enumerate}
  \item Use MOP definitions to create \emph{host classes} and \emph{host generic
    functions} (accessors).
  \item Use MOP definitions again to create \emph{bridge classes} and
    \emph{bridge generic functions}.  
  \item Use MOP definitions again to create \emph{ersatz classes} and
    \emph{ersatz generic functions}.  
  \item Replace references to bridge objects in ersatz objects by
    references to ersatz objects.
  \item Create target objects as a graph that is \emph{isomorphic} to
    the graph of ersatz objects.
  \end{enumerate}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{CLOS Bootstrapping}
  \framesubtitle{Satiation}

Given a set of classes, satiating a generic function fills its call
history with all possible effective methods that can result from calls
with arguments that are instances of those classes. 
\vskip 0.5cm
Satiation does not create metastability problems because the dispatch
machinery is always executed by the \emph{previous step} in the
bootstrapping sequence.
\end{frame}
%-----------------------------------------------------------
%-----------------------------------------------------------
%-----------------------------------------------------------
%-----------------------------------------------------------
\begin{frame}
  \frametitle{SICL}
  \framesubtitle{Current state}
Finished:
\vskip 0.25cm
\begin{itemize}
\item Implementation-independent \texttt{cons} operators. 
\item Implementation-independent \texttt{string} operators.
\end{itemize}
\vskip 0.5cm
Almost finished:
\vskip 0.25cm
\begin{itemize}
\item \texttt{format}
\item CLOS
\item \texttt{loop}
\item Reader
\end{itemize}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{SICL}
  \framesubtitle{Currently being worked on}

A library inspired by LLVM for compilation and optimization called
\emph{Cleavir}: 

\begin{itemize}
\item Representation of program as a graph of instructions (\emph{flow
  chart} or \emph{flow graph})
\item Collection of state-of-the-art transformations and
  optimizations:
  \begin{itemize}
  \item Conversion to static single assignment form.
  \item Common subexpression elimination.
  \item Value numbering.
  \item Loop optimizations.
  \item Escape analysis.
  \item Register allocation.
  \item etc.
  \end{itemize}
\item Implementation-specific extensions using CLOS.
\item Backends for common architectures.
\end{itemize}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{SICL}
  \framesubtitle{Future}

Near(ish):
\begin{itemize}
\item Rudimentary compiler.
\item Backend for x86-64.
\end{itemize}
\vskip 0.5cm
  
A few years:
\begin{itemize}
\item The rest of CLHS.
\item Standard compiler optimizations.
\end{itemize}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{SICL}
  \framesubtitle{Future}

Research:

\begin{itemize}
\item Per-region register allocation.
\item Selective use of common subexpression elimination and global
  value numbering so as to decrease demands for registers.
\item Global garbage collection.
\item Call-site optimization techniques. 
\end{itemize}

\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{SICL}
  \framesubtitle{Future}
Later:
\begin{itemize}
\item Multi-user system based on first-class global environments. 
\item A Lisp Operating System.
\end{itemize}
\end{frame}
%-----------------------------------------------------------
\begin{frame}
  \frametitle{That's all folks}
  
Questions?
\vskip 0.5cm
https://github.com/robert-strandh/SICL

  \begin{center}
\inputfig{lizard.pdf_t}
  \end{center}

\end{frame}
%-----------------------------------------------------------
%-----------------------------------------------------------
\end{document}

%%  LocalWords:  metastability
